
/**
 * @author 
 * Yannic Remmet			196983
 * Tobias Trabelsi			197112
 * Anna-Katharina Wickert	197122
 */

public class MergeSort {
	public static Comparable[] mergeSort(Comparable[] a ){

		array = a;
		if(a.length <= 1)
			return a;
		int middle = a.length/2;
		
		Comparable[] left = new Comparable[middle];
		for (int i=0; i < middle; i++) 
			left[i] = a[i];
		//Debugging
		System.out.print("mergeSort 22: ");
		for (int i=0; i < left.length; i++)
			System.out.print(" " + left[i] + " ");
		System.out.println();
		
		Comparable[] right = new Comparable[a.length - middle];
		for (int i=0; i < right.length; i++)
			right[i] = a[middle + i];
		//Debugging
		System.out.print("mergeSort 22: ");
		for (int i=0; i < right.length; i++)
			System.out.print(" " + right[i] + " ");
		System.out.println();
		
		left = mergeSort(left);
		right = mergeSort(right);
		
		return merge(left, right); 
		
	}
	
	private static Comparable[] merge(Comparable[] left, Comparable[] right){
		System.out.print("merge beginning: left: ");
		for (int i= 0; i < left.length; i++)
			System.out.print(" " + left[i] + " ");
		System.out.print(" right: " );
		for (int i= 0; i < right.length; i++)
			System.out.print(" " + right[i] + " " );
		System.out.println();
		Comparable[] newList = new Comparable[array.length];
		int index = 0;
		System.out.println("Index: " + index + " left.length: "+ left.length + " right.length: "+ right.length);
		while(left.length != 0 && right.length != 0) {
			System.out.println("Index: " + index + " left.length: "+ left.length + " right.length: "+ right.length);
			System.out.println("left[0]: " + left[0] + " right[0] " + right[0]);
			if (left[0].compareTo(right[0]) <= 0) {
				help = new Comparable[newList.length];
				for (int i=0; i<newList.length; i++)
					help[i]	 = newList[i];
				newList = new Comparable[help.length + 1];
				for (int i=0; i < help.length; i++)
					newList[i] = help[i];
				newList[index] = left[0];
				help = new Comparable[left.length];
				System.out.println("merge 67: help.length: " + help.length + " left.length: " + left.length + " newList.length " + newList.length);
				System.arraycopy(left, 0, help, 0, left.length);
				left = new Comparable[help.length -1];
				for (int i=0; i < left.length; i++)
					left[i] = help[i+1];
				index++;
				System.out.print("merge kleiner: ");
				for (int i=0; i < newList.length; i++)
					System.out.print(" " + newList[i] + " ");
				System.out.println();
			}
			else {
				help = new Comparable[newList.length];
				for (int i=0; i<newList.length; i++)
					help[i]	 = newList[i];
				newList = new Comparable[help.length + 1];
				for (int i=0; i < help.length; i++)
					newList[i] = help[i];
				newList[index] = right[0];
				help = new Comparable[right.length];
				System.arraycopy(right, 0, help, 0, right.length);
				right = new Comparable[help.length -1];
				for (int i=0; i < right.length; i++)
					right[i] = help[i+1];
				index++;
				System.out.print("merge größer: ");
				for (int i=0; i < newList.length; i++)
					System.out.print(" " + newList[i] + " ");
				System.out.println();
			}
			System.out.print("newList Content: ");
			for (int i=0; i < newList.length; i++ )
				System.out.print(newList[i]);
			System.out.println();
		}
		System.out.println("merge 73: left.length: "+ left.length + " right.length: " + right.length);
		while(left.length != 0) {
			newList[index] = left[0];
			help = new Comparable[left.length];
			System.arraycopy(left, 0, help, 0, left.length);
			left = new Comparable[left.length -1];
			for (int i=0; i < left.length; i++)
				left[i] = help[i+1];
			index++;
			System.out.print("newList Content: ");
			for (int i=0; i < newList.length; i++ )
				System.out.print(newList[i]);
			System.out.println();
		}
		
		System.out.println("merge 82: left.length(0) "+ left.length + " right.length: " + right.length + " index: " + index + " newList.length " + newList.length);
		while(right.length != 0) { 
			newList[index] = right[0];
			help = new Comparable[right.length];
			System.arraycopy(right, 0, help, 0, right.length);
			right = new Comparable[right.length -1];
			for (int i=0; i < right.length; i++)
				right[i] = help[i+1];
			index++;
			System.out.print("newList Content: ");
			for (int i=0; i < newList.length; i++ )
				System.out.print(newList[i]);
			System.out.println();
		}
		return newList;	
				
	}
	
	// data-elements
	private static Comparable[] array;
	private static Comparable[] help;
}
